package bintree.map_set.leetcode;

import java.util.*;

class Pair{
    public Pair(int u, int v) {
        this.u = u;
        this.v = v;
    }

    int u;
    int v;
}
public class Num373查找和最小的K对数字 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
// 1.创建优先级队列，其中队列中保存Pair对象，传入比较器，和越小反而越大
        Queue<Pair> queue= new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return (o2.u+o2.v)-(o1.u + o1.v);
            }
        });
        // 2.遍历两个数组，其中u来自第一个数组，v来自第二个数组
        // 队列中保存了和最小的k个数对
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j <Math.min(nums2.length,k); j++) {
                if (queue.size()<k){
                   queue.offer(new Pair(nums1[i],nums2[j] ));
                }else {
                    int add=nums1[i]+nums2[j];
                    Pair pair = queue.peek();
                    if (add<(pair.u+ pair.v)){
                        queue.poll();
                        queue.offer(new Pair(nums1[i],nums2[j] ));
                    }
                }

            }
        }
        List<List<Integer>> ret = new ArrayList<>();
        while (!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            Pair pair = queue.poll();
            temp.add(pair.u);
            temp.add(pair.v);
            ret.add(temp);
        }
        return  ret;
    }
}
